翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

quadratic residuosity problem : ウィキペディア英語版
quadratic residuosity problem
The quadratic residuosity problem in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are not obviously quadratic non-residues (see below).
The problem was first described by Gauss in his ''Disquisitiones Arithmeticae'' in 1801.
This problem is believed to be computationally difficult.
Several cryptographic methods rely on its hardness, see Applications.
An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether a composite N of unknown factorization is the product of 2 or 3 primes
.
== Precise formulation ==

Given integers a and T, a is said to be a ''quadratic residue modulo T'' if there exists an integer b such that
:a \equiv b^2 \pmod T.
Otherwise we say it is a quadratic non-residue.
When T = p is a prime, it is customary to use the Legendre symbol:
:\left(\frac\right) =
\begin
1 & \text a \text p \text a \not\equiv 0\pmod, \\
-1 & \text a \text p, \\
0 & \text a \equiv 0 \pmod.
\end
This is a multiplicative character which means \big(\tfrac\big) = 1 for exactly (p-1)/2 of the values 1,\ldots,p-1, and it is -1 for the remaining.
It is easy to compute using the law of quadratic reciprocity in a manner akin to the Euclidean algorithm, see Legendre symbol.
Consider now some given N = p_1 p_2 where p_1 and p_2 are two, different unknown primes.
A given a is a quadratic residue modulo N if and only if a is a quadratic residue modulo both p_1 and p_2.
Since we don't know p_1 or p_2, we cannot compute \big(\tfrac\big) and \big(\tfrac\big).
Perhaps surprisingly, however, we can easily compute their product!
This is known as the Jacobi symbol:
:
\left(\frac\right) = \left(\frac\right)\left(\frac\right)

This can also be efficiently computed using the law of quadratic reciprocity for Jacobi symbols.
However, \big(\tfrac\big) can not in all cases tell us whether a is a quadratic residue modulo N or not!
More precisely, if \big(\tfrac\big) = -1 then a is necessarily a quadratic non-residue modulo either p_1 or p_2, in which case we are done.
But if \big(\tfrac\big) = 1 then it is either the case that a is a quadratic residue modulo both p_1 and p_2, or a quadratic non-residue modulo both p_1 and p_2.
We cannot distinguish these cases from knowing just that \big(\tfrac\big) = 1.
This leads to the precise formulation of the quadratic residue problem:
Problem:
Given integers a and N = p_1 p_2, where p_1 and p_2 are unknown, different primes, and where \big(\tfrac\big) = 1, determine whether a is a quadratic residue modulo N or not.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「quadratic residuosity problem」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.